// 二叉树是一种从上往下的树状结构的数据结构，从根节点开始每个节点最多有两个子节点，
//
// 分别是：左边的为左子节点，右边的为右子节点。
//
// 排序二叉树是有顺序的，且没有重复元素的二叉树。顺序为：
//
// 对每个节点而言：
//
// 1）如果左子树不为空，则左子树上的所有节点都小于该节点；
//
// 2）如果右子树不为空，则右子树上的所有节点都大于该节点；


// 运用场景：
// 可以用在全文搜索一个内容时， 比如一个文章中你需要查找的内容出现在哪一行或者哪个位置，
//比如海量数据并发查询，  在数据压缩上有重要应用， 提高了传输的有效性。在处理大批量的动态的数据是比较有用。
//首创建节点
class CreatNode {
    constructor(key) {
        // 设置插入值
        this.key = key;
        // 左叉树
        this.left = null;
        // 右叉树
        this.right = null;
    }
}
//然后创建二叉树 (BST)）
class CreatBinaryTree {
    constructor() { // 设置根节点
        this.rootNode = null;
    }
    // 在排序二叉树中，插入元素首先要找插入位置，即新节点的父节点。
    //
    // 与查找元素类似从根节点开始找：
    //
    // 1）与当前节点相同，则已经存在了，不能插入；
    //
    // 2）如果小于当前节点，则到左子树中查找，如果左子树为空，则当前节点为要找到的父节点；
    //
    // 3）如果大于当前节点则到右子树中查找，如果右子树为空，则当前节点为要找的父节点。
    // 插入节点
    insert(node) {
        const newNode = new CreatNode(node);
        // 插入叶子节点
        const insertNode = (parentNode, newNode) => {
            // 新节点和老节点 如果新节点比老节点小  就把新节点放在左边
            if (newNode.key < parentNode.key) {
                // 判断如果左节点没有子节点
                if (parentNode.left === null) {
                    parentNode.left = newNode;
                } else {
                    // 如果有老节点有左子节点 就在左子节点的左边递归添加
                    insertNode(parentNode.left, newNode)
                }
            } else {
                // 如果新节点比老节点大  就把新节点放在在右边
                if (parentNode.right === null) {
                    parentNode.right = newNode;
                } else {
                    // 如果有老节点有右子节点 就在右子节点的右边递归添加
                    insertNode(parentNode.right, newNode)
                }
            }
        }
        // 判断根（父）节点是否为null
        if (this.rootNode == null) {
            // 新节点的值赋给父节点
            this.rootNode = newNode;
        } else {
            // 不为空时就往下插入数据节点
            // 插入节点要和父节点root对比  设置一个对比函数
            insertNode(this.rootNode, newNode);
        }
    }
     // 三种遍历  中序遍历 前序遍历  后序遍历
    //中序遍历  升序或降序
    inOrder() {
        let callbackArr = [];
        const inOrderNode = (node, callback) => {
            if (node !== null) {
                // 递归访问左子树一直访问到为空       然后返回到当前的父节点
                inOrderNode(node.left, callback);
                // 返回 访问当前父节点的key值添加到数组里
                callbackArr.push(callback(node.key));
                // 递归访问右子树一直访问到为空       然后返回到当前的父节点
                inOrderNode(node.right, callback);
            }
        };
        // 每个节点的回调函数
        // 先从父节点遍历查找子节点是否为null和每个节点的回调函数 对比
        inOrderNode(this.rootNode, (key) => {
            return key;
        });
        return callbackArr;
    }
    //前序遍历 作用当有个二叉树时重新复制一份二叉树
    preOrder() {
        let callbackArr = [];
        const preOrderNode = (node, callback) => {
            if (node !== null) {
                // 先访问当前节点输出当前节点然后再去访问左节点一直到null再去访问右节点。

                // 直接访问当前父节点的key值添加到数组里
                callbackArr.push(callback(node.key));
                // 然后递归查看左子节点有没有叶子节点
                preOrderNode(node.left, callback);
                // 然后递归查看右子节点有没有叶子节点
                preOrderNode(node.right, callback)
            }
        };
        preOrderNode(this.rootNode, (key) => {
            return key;
        });
        return callbackArr;
    }
    //后序遍历
    postOrder() {
        let callbackArr = [];
        const postOrderNode = (node, callback) => {
            if (node !== null) {
                // 优先输出左子树一直到最后到叶子节点，，然后寻找右子树 然后返回中间节点
                // 先访问左右子节点有没有叶子节点
                // 然后递归查看左子节点有没有叶子节点
                postOrderNode(node.left, callback);
                // 然后递归查看右子节点有没有叶子节点
                postOrderNode(node.right, callback);
                // 最后访问到没有左右子节点了添加进去
                callbackArr.push(callback(node.key))
            }
        };
        postOrderNode(this.rootNode, (key) => {
            return key;
        });
        return callbackArr;
    }
    // 1.查找
    // 1）首先与根节点比较，相同则找到；
    //
    // 2）如果小于根节点，则到左子树种递归查找；
    //
    // 3）如果大于根节点，则到右子树中递归查找；
    //
    // 这个步骤与在数组中进行二分查找是类似的。此外，在排序二叉树中查找最大值和最小值很简单。
    //查找最小值
    getMinNum(node) {
        const minNode = node => {
            //  从左子节点找最小值
            return node ? (node.left ? minNode(node.left) : node.key) : null
        };
        return minNode(node || this.rootNode)
    }
    //查找最大值
    getMaxNum(node) {
        const maxNode = node => {
            //  从右子节点找最大值
            return node ? (node.right ? maxNode(node.right) : node.key) : null
        };
        return maxNode(node || this.rootNode)
    }


    //查找特定值
    getFindNum(data) {
        const findNode = (node, data) => {
            if (node === null) return false; //如果根节点不存在就返回false
            // 要查找的值小于当前节点的值，用左子树继续查找
            if (data < node.key) {
                return findNode(node.left, data);
            } else if (data > node.key) {
                // 要查找的值大于当前节点的值，用右子树继续查找
                return findNode(node.right, data);
            } else {
                return true;
            }
        };
        return findNode(this.rootNode, data)
    }

    //
    // 从排序二叉树中删除一个节点，主要有三种情况：
    //
    // 1）节点为叶子节点: 直接删除
    //
    // 2）节点只有一个孩子节点：
    //
    // 删除当前节点，让其子节点与父节点建立链接

    //删除某节点值
    remove(data) {
        const removeNode = (node, data) => {
            if (node === null) return null; //如果不存在就返回null
            // 要查找的值小于当前节点的值，用左子树继续查找
            if (data < node.key) {
                node.left = removeNode(node.left, data);
                return node;
            } else if (data > node.key) {
                // 要查找的值大于当前节点的值，用右子树继续查找
                node.right = removeNode(node.right, data);
                return node;
            } else {
                if (node.left === null && node.right === null) return null;
                if (node.left === null) return node.right;
                if (node.right === null) return node.left;
                //在右子树中找到最小值节点
                var _node = this.getMinNum(node.right);
                // 将_node最小值节点的值更新为node最小值节点的值
                node.key = _node.key;
                // 因为最小值节点在右子树中 所以要从右子树中查找删除
                node.right = removeNode(node.right, node.key);
                // 然后返回节点
                return node;
            }
        };
        return removeNode(this.rootNode, data)
    }
}

// 实例化
const binaryTree = new CreatBinaryTree();
//

// // 一、 插入节点 这里单个 一个一个插入
// binaryTree.insert(16);
// binaryTree.insert(9);
// binaryTree.insert(15);
// binaryTree.insert(4);
// binaryTree.insert(16);
// binaryTree.insert(18);
// binaryTree.insert(14);
// binaryTree.insert(17);
// binaryTree.insert(11);
// binaryTree.insert(17);
// binaryTree.insert(24);
// binaryTree.insert(17);
// binaryTree.insert(28);
// // 二、 设置一个数组批量插入
// var nodeList = [16,15, 4, 18, 14, 17, 24,28,2];
// nodeList.forEach((key) => {
//     binaryTree.insert(key);
// });
// console.log("tree", binaryTree); //得到二叉树结构
// binaryTree.inOrder(); //中序排列   【4, 9, 11, 14, 15, 16, 16, 17, 17, 17, 18, 24, 28 ]
// console.log(binaryTree.preOrder()); //前序排列   [ 16, 9, 4, 15, 14, 11, 16, 18, 17, 17, 17, 24, 28 ]
// console.log(binaryTree.postOrder()); //后序排列   [ 4, 11, 14, 15, 9, 17, 17, 17, 28, 24, 18, 16, 16 ]
// console.log(binaryTree.getMinNum()); //查找最小值   4
// console.log(binaryTree.getMaxNum()); //查找最大值  28
// console.log(binaryTree.getFindNum(12)); //查找最大值   false
// console.log(binaryTree.getFindNum(28)); //查找特定值   true
// console.log(binaryTree.remove(4)); ////删除某值  节点    true
